import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int array[] = {8,3,6,5,1,2,9,0,4,7};
        int temp = 0;

        //希尔排序法（移位式）
        //注意：交换式排序所需时间要大于插入排序，使用移位式速度更快
        //每轮以array.length()/2的间隔分组
        for(int gap = array.length/2; gap > 0; gap /= 2){
            //每一次分组后采用插入排序法
            for(int index = 1; index < array.length; index += gap){
                 int leftindex = index - gap;
                 temp = array[index];
                 while(leftindex >= 0 && array[leftindex] > temp){
                     array[leftindex + gap] = array[leftindex];
                     leftindex -= gap;
                 }
                 array[leftindex + gap] = temp;
            }
        }
        System.out.println(Arrays.toString(array));
    }
}
